import json
InputStr = '''
[
    {
        "node": "AND",
        "children": [
            {
                "node": "a"
            },
            {
                "node": "==",
                "children": [
                    {
                        "node": "d"
                    },
                    {
                        "node": "OR",
                        "children": [
                            {
                                "node": "b"
                            },
                            {
                                "node": "c"
                            }
                        ]
                    }
                ]
            }
        ]
    }
]
'''
# 将JSON格式输入字符串转换为Python数据类型
InputDataTree = json.loads(InputStr)
print(InputDataTree)
# output:
#[{'node': 'AND', 'children': [{'node': 'a'}, {'node': '==', 'children': [{'node': 'd'}, {'node': 'OR', 'children': [{'node': 'b'}, {'node': 'c'}]}]}]}]

# 给定的嵌套字典结构
data = [{'node': 'AND', 'children': [{'node': 'a'}, {'node': '==', 'children': [{'node': 'd'}, {'node': 'OR', 'children': [{'node': 'b'}, {'node': 'c'}]}]}]}]

# 遍历InputDataTree，并打印每个节点的值


def traverse(node):
    # 打印当前节点的值
    print(node['node'])
    # 如果存在children，则递归遍历每一个子节点
    if 'children' in node:
        for child in node['children']:
            traverse(child)


# 开始遍历
traverse(data[0])
# output
# AND
# a
# ==
# d
# OR
# b
# c

def to_postfix(node):
    """
    将中缀表达式树转换为后缀表达式（逆波兰表达式）。

    Args:
        node (dict): 中缀表达式树的节点，包含'node'键和'children'键。'node'键存储节点值（操作符或操作数），'children'键存储子节点列表。

    Returns:
        str: 转换后的后缀表达式。

    """
    postfix = ''
    if 'children' in node:
        # 递归处理子节点
        for child in node['children']:
            postfix += to_postfix(child)
        # 添加当前节点的值（操作符）
        postfix += (node['node']+',')
    else:
        # 如果没有子节点，直接添加节点值（操作数）
        postfix += (node['node']+',')
    return postfix


# 将树转换为后缀表达式
postfix_expression = to_postfix(data[0])
print(postfix_expression)
# output:
# a,d,b,c,OR,==,AND,


# 给定的后缀表达式
postfix_expression = "a,d,b,c,OR,==,AND,"

# 将后缀式转换为三元式
def to_triplet(postfix_expr):
    stack = []
    triplets = []
    operators = ['OR', '==', 'AND']
    seq = 1  # 初始化三元式编号
    tokens = postfix_expr.split(',')
    for token in tokens:
        if token not in operators:  # 非运算符
            stack.append(token)
        if token in operators:  # 运算符
            if token in operators:  # 二元运算符
                opnd2 = stack.pop()
                opnd1 = stack.pop()
                noStr = '(' + str(seq) + ')'
                seq = seq + 1
                triplets.append((noStr, token, opnd1, opnd2))
                stack.append(noStr)
    return triplets
# 将后缀表达式转换为三元式
triplets = to_triplet(postfix_expression)
print(triplets)
# output
# [
# ('(1)', 'OR', 'b', 'c'), 
# ('(2)', '==', 'd', '(1)'),
# ('(3)', 'AND', 'a', '(2)')
# ]


# 将后缀式转换为四元式
def to_quadruple(postfix_expr):
    stack = []
    quadruples = []
    operators = ['OR', '==', 'AND']
    seq = 1  # 初始化三元式编号
    tokens = postfix_expr.split(',')
    for token in tokens:
        if token not in operators:  # 非运算符
            stack.append(token)
        if token in operators:  # 运算符
            if token in operators:  # 二元运算符
                opnd2 = stack.pop()
                opnd1 = stack.pop()
                noStr = 'T' + str(seq) 
                seq = seq + 1
                quadruples.append((token, opnd1, opnd2,noStr))
                stack.append(noStr)
    return quadruples


# 将后缀表达式转换为三元式
quadruples = to_quadruple(postfix_expression)
print(quadruples)
# output
# [
# ('OR', 'b', 'c', 'T1'), 
# ('==', 'd', 'T1', 'T2'), 
# ('AND', 'a', 'T2', 'T3')
# ]